/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 言初
 * Date: 2023-12-25
 * Time: 22:20
 */
import java.util.Scanner;


public class Main13 {


    //多段图 的最短路径问题

    public static void backPath(int n ,int m, int[][] array){

        if(n==0){
            return;
        }

        //求解最短路径问题
        int[] cost=new int[n];//存储从起点到每一个下标点的最短路径的值
        int[] path=new int[n];//path[i]存储的是：到达i下标点的这条最短路径中 i 下标的前一个点的下标

        //本题要求解的最短路径，所以说：新创建的2个数组都需要进行相应的新的初始化操作
        // 对于存下标的path数组，应该让其内部存储的值 都 是非法的值，那就让它存-1，这样在方便后续的操作了
        for(int i=0;i<n;i++){
            path[i]=-1;
        }
        //对于存路径距离的cost数组，因为它要存的是最短路径嘛，所以把它内部的值初始化的很大，方便后续的操作
        for(int i=0;i<n;i++){
            cost[i]=Integer.MAX_VALUE;
        }

        cost[0]=0; // 这里对0下标的对应位置进行了初始化的设定,0下标到0下标的距离值当然就是0了
        path[0]=-1;// 这里对0下标的对应位置进行了初始化的设定，0下标的前一个位置是不存在的，所以这里设置为-1了

        //从下标为0的位置到下标为n-1的位置的最短路径
        //0下标为起始，单独作为第一段，所有和0下标有边的关联的点作为第二段，依次类推


        //j代表列，i代表行
        //接下来的这个for循环，原理就是： 找到一个点   ret   它的前面的所有和它   有 边 的关联的   点 ，
        // 一个小小的要求，ret>k，所以要去ret的前面的点中去找( 这里的ret也就相当于下面的j,这里的k也就相当于下面的i )
        //然后通过这些点的  最短路径cost[k] 加上这些点各自到达这个点的距离的 array[k][ret] 这些点中在找到一个最小值作为 ，这个点的最短路径的值 cost[ret]

        for(int j=1;j<n;j++){
            for(int i=j-1;i>=0;i--){
                int dis=Integer.MAX_VALUE;
                if(array[i][j] != Integer.MAX_VALUE){
                    // 如果此时这条边的值array[i][j] 不为 Integer.MAX_VALUE ，
                    // 那就说明 这条边是存在的，在求解的过程中就可以使用到这条边，所以进入if语句
                    dis=cost[i]+array[i][j];
                }else{
                    // 如果此时这条边的值array[i][j] 为Integer.MAX_VALUE ，
                    // 那就说明 这条边是不存在的，所以就跳过这条不存在的边，继续求去找下一条边去，所以使用了continue
                    continue;
                }

                if(dis < cost[j]){
                    // 找最小值的比较过程
                    cost[j]=dis;
                    path[j]=i;
                }
            }
        }


        //打印这个从0下标到n-1下标的最短路径的值
        System.out.println(cost[n-1]);


    }









    public static void main(String[] args) {
        //支持输入这个图的关系的方案
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();//顶点的个数
        int m=sc.nextInt();//这个图的有效边的个数
        int[][] array=new int[n][n];

        //对图的初始化
        //n是点的个数，m是边的个数
        //这个函数是用来建立多段图的代价矩阵的
        //使用一个二维数组来接受点之间的权值关系
        // int[][] array=new int[n][n];
        //我们要求的是最短路径，所以把没有关联的点之间的距离设为最大值，这样就不会用到这些不存在的边了
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                array[i][j]=Integer.MAX_VALUE;
            }
        }

        //真正开始   初始化各个点之间的边的权值
        for(int p=0;p<m;p++){
            int i=sc.nextInt()-1;
            int j= sc.nextInt()-1;
            array[i][j]=sc.nextInt();
        }


        backPath(n,m,array);
    }

}
